package Demo4;

public class CircularQueue {

    static class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    // 队尾指针指向链表的最后一个节点
//    循环队列 rear.next 为 队头
    private Node rear = null;


    public void clearQueue() {
        rear = null;
    }

    public boolean isEmpty() {
        return rear == null;
    }

//     入队操作
    public void enqueue(int data) {
        Node newNode = new Node(data);
        if (isEmpty()) {
            // 如果队列为空，队尾指针指向新节点，且形成自环
            rear = newNode;
            rear.next = rear;
        } else {
            newNode.next = rear.next;
            rear.next = newNode;      // 原队尾的next指向新节点
            rear = newNode;           // 更新队尾指针为新节点
        }
    }


    // 出队操作
    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空，无法出队");
        }

        Node front = rear.next;
        if (rear == rear.next) {
            // 如果队列中只有一个元素，出队后队列为空
            rear = null;
        } else {
            rear.next = front.next; // 队尾指针的next指向原队头的下一个节点
        }
        return front.data; // 返回出队元素
    }

    // 打印队列
    public void printQueue() {
        if (isEmpty()) {
            System.out.println("队列为空");
            return;
        }
        Node temp = rear.next;  // 从队头开始打印
        do {
            System.out.print(temp.data + " ");
            temp = temp.next;
        } while (temp != rear.next); // 遍历整个循环链表
        System.out.println();
    }

    public static void main(String[] args) {
        CircularQueue queue = new CircularQueue();

        // 入队操作
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        queue.printQueue();

        // 出队操作
        System.out.println("出队: " + queue.dequeue());
        queue.printQueue();

        // 再次入队
        queue.enqueue(4);
        queue.printQueue();

        // 置队空
        queue.clearQueue();
        queue.printQueue();
    }
}
